package com.ocean.stack;

import java.util.*;

/**
 * https://leetcode.cn/problems/valid-parentheses/
 * 有效的括号
 */
public class ValidParentheses {
    public static void main(String[] args) {
        ValidParentheses validParentheses = new ValidParentheses();
        String str  =  "([{}]))";
        System.out.println(validParentheses.isValid(str));
    }

    public boolean isValid(String s) {
        int length = s.length();
        if (length % 2 == 1) {
            return false;
        }
        Map<Character, Character> map = new HashMap<Character, Character>() {
            {
                put(']', '[');
                put(')', '(');
                put('}', '{');
            }
        };
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                if (stack.isEmpty() || stack.peek() != map.get(c)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}
